// https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=30
// 2024-10-23

public class P035_字符串搜索_哈希算法 {

    public static void main(String[] args) {
        String txt = "ABCABCAABCABCD";
        String pat = "ABCABCD";

        System.out.println(RK(txt,pat));
    }

    private static int RK(String txt, String pat) {
        // 求前pat.length长度的和
        int sum_txt = 0,sum_pat = 0;
        for (int i = 0; i < pat.length(); i++) {
            sum_pat += pat.charAt(i);
            sum_txt += txt.charAt(i);
        }

        int i = 0,j = pat.length()-1;
        while (j <= txt.length() - 1) {
            if (sum_txt == sum_pat) {
                // 说明哈希值一样，逐个比较
                int k = i;
                for (; k <= j ; k++) if (pat.charAt(k-i) != txt.charAt(k)) break;
                if (k > j) return i;   //子串全部匹配完了
            }
            sum_txt -= txt.charAt(i);
            i++;
            j++;
            sum_txt += txt.charAt(j);
        }
        return -1;
    }

}
